/* List.cs -- 
   Copyright (C) 2007, 2008  Casey Marshall.
   Copyright (C) 2008 Pacific Biosciences, Inc.

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */


using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace SexpSharp
{
    public class List : Expression, IList<Expression>, ICloneable
    {
		public const int MAX_LINE_LENGTH = 80;

		private Expression child;
		protected int modcount;

		private List(Expression child)
		{
			this.child = child;
		}

		public List()
		{
		}

		public Expression Child
		{
			get
			{
				return this.child;
			}
		}

#region IList<Expression> implementation
    
		// <summary>
		// Fetch the indexed item in this list. Has O(n) complexity.
		// </summary>
		public Expression this[int index]
		{
			get
			{
				if (index < 0)
					throw new ArgumentOutOfRangeException();
				Expression cur = this.child;
				int i;
				for (i = 0; i < index && cur != null; i++)
					cur = cur.Next;
				if (i == index && cur != null)
					return cur;
				throw new ArgumentOutOfRangeException();
			}

			set
			{
				if (index < 0)
					throw new ArgumentOutOfRangeException();
				Expression _value = (Expression) value;
				Expression cur = this.child;
				int i;
				for (i = 0; i < index && cur != null; i++)
					cur = cur.Next;
				if (i == 0)
				{
					child = _value;
					child.next = cur.next;
					child.previous = null;
					child.parent = this;
					cur.next = null;
					cur.previous = null;
					cur.parent = null;
				}
				else if (i == index && cur != null)
				{
					cur.previous.next = _value;
					_value.next = cur.next;
					cur.previous = null;
					cur.next = null;
					cur.parent = null;
				}
				else
					throw new ArgumentOutOfRangeException();
				modcount++;
			}
		}

		public void Insert(int index, Expression item)
		{
			Expression cur = child;
			int i;
			for (i = 0; i < index && cur != null; i++)
				cur = cur.Next;
			if (i == 0)
			{
				item.next = child;
				item.previous = null;
				item.parent = this;
				this.child = item;
			}
			else if (i == index && cur != null)
			{
				item.next = cur;
				item.previous = cur.previous;
				item.parent = this;
				cur.previous.next = item;
				cur.previous = item;
			}
			else
				throw new ArgumentOutOfRangeException();
			modcount++;
		}

		public void Clear()
		{
			child = null;
		}

		public bool Contains(Expression item)
		{
			if (child == null)
				return false;
			Expression e = child;
			while (e != null)
			{
				if (e == item)
					return true;
				e = e.Next;
			}
			return false;
		}

		public int IndexOf(Expression item)
		{
			if (child == null)
				return -1;
			int i = 0;
			Expression e = child;
			while (e != null)
			{
				if (e == item)
					return i;
				e = e.Next;
				i++;
			}
			return -1;
		}

		public void RemoveAt(int index)
		{
			if (index == 0)
			{
				if (child != null)
				{
					child = child.Next;
					if (child != null)
						child.previous = null;
				}
				return;
			}
			int i = 0;
			Expression e = child;
			while (e != null)
			{
				if (i == index)
				{
					e.Previous.next = e.Next;
					if (e.Next != null)
						e.Next.previous = e.Previous;
					return;
				}
			}
		}

		public bool IsFixedSize
		{
			get { return false; }
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

#endregion

#region ICollection<Expression> implementation.

		public int Count
		{
			get
			{
				int i;
				Expression cur = child;
				for (i = 0; cur != null; i++)
					cur = cur.Next;
				return i;
			}
		}

		public bool IsSynchronized
		{
			get { return false; }
		}

		public override object SyncRoot
		{
			get
			{
				if (parent == null)
					return this;
				return parent.SyncRoot;
			}
		}

		public void Add(Expression item)
		{
			if (child == null)
			{
				child = item;
				modcount++;
			}
			else
			{
				Expression cur = child;
				int i = 0;
				while (cur.Next != null)
				{
					cur = cur.Next;
					i++;
				}
				cur.next = item;
				item.previous = cur;
				item.next = null;
				item.parent = this;
				modcount++;
			}
		}

		public void CopyTo(Expression[] array, int index)
		{
			foreach (Expression e in this)
				array[index++] = e;
		}

		public bool Remove(Expression item)
		{
			if (item == child)
			{
				child = child.Next;
				if (child != null)
					child.previous = null;
				return true;
			}
			Expression e = child;
			while (e != null)
			{
				if (e == item)
				{
					e.previous = e.Next;
					if (e.Next != null)
						e.Next.previous = e.Previous;
					return true;
				}
				e = e.Next;
			}
			return false;
		}

#endregion

#region IEnumerable<Expression> implementation.

		private sealed class Enumerator : IEnumerator<Expression>
		{
			private List list;
			private Expression cur;
			private int modcount;
			private bool end;
			internal Enumerator(List l) { list = l; modcount = list.modcount; end = false; }

			public void Dispose()
			{
			}

			public Expression Current
			{
				get
				{
					if (modcount != list.modcount)
						throw new InvalidOperationException("list was modified");
					return cur;
				}
			}

			object System.Collections.IEnumerator.Current
			{
				get { return Current; }
			}

			public bool MoveNext()
			{
				if (modcount != list.modcount)
					throw new InvalidOperationException("list was modified");
				if (end)
					return false;
				if (cur == null)
					cur = list.child;
				else
					cur = cur.next;
				if (cur == null)
				{
					end = true;
					return false;
				}
				return true;
			}

			public void Reset()
			{
				end = false;
				cur = null;
			}
		}

		public IEnumerator<Expression> GetEnumerator()
		{
			return new Enumerator(this);
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

#endregion

		public override object Clone()
		{
			List copy = new List();
			Expression cur = null;
			for (IEnumerator<Expression> it = this.GetEnumerator(); it.MoveNext(); )
			{
				Expression e = (Expression) it.Current.Clone();
				if (cur == null)
				{
					copy.child = e;
					e.next = null;
					e.previous = null;
				}
				else
				{
					cur.next = e;
					e.next = null;
					e.previous = cur;
				}
				cur = e;
				e.parent = copy;
			}
			return copy;
		}

		public override void WriteVerbatim(Stream o)
		{
			o.WriteByte((byte) '(');
			for (Expression e = child; e != null; e = e.Next)
				e.WriteVerbatim(o);
			o.WriteByte((byte) ')');
		}

		public override string ToString()
		{
			return ToAdvancedString(0, 0);
		}

		public override string ToAdvancedString()
		{
			return ToAdvancedString(0, 0);
		}

		public string ToAdvancedString(int indent, int line_len)
		{
			StringBuilder str = new StringBuilder();
			str.Append('(');
			indent++;
			line_len++;
			for (Expression e = child; e != null; e = e.Next)
			{
				if (e is List)
				{
					string s = (e as List).ToAdvancedString(indent, line_len);
					if (s.IndexOf('\n') >= 0)
					{
						if (e != child)
							str.Append(' ');
						str.Append(s);
						line_len = s.Length - s.LastIndexOf('\n');
					}
					else
					{
						if (line_len + s.Length > MAX_LINE_LENGTH)
						{
							str.Append('\n');
							indent.Times(delegate () { str.Append(' '); });
							str.Append(s);
							line_len = indent + s.Length;
						}
						else
						{
							if (e != child)
							{
								line_len++;
								str.Append(' ');
							}
							str.Append(s);
							line_len += s.Length;
						}
					}
				}
				else
				{
					string s = e.ToAdvancedString();
					if (line_len + s.Length > MAX_LINE_LENGTH)
					{
						str.Append('\n');
						indent.Times(delegate () { str.Append(' '); });
						str.Append(s);
						line_len = indent + s.Length;
					}
					else
					{
						if (e != child)
						{
							line_len++;
							str.Append(' ');
						}
						str.Append(s);
						line_len += s.Length;
					}
				}
			}
			str.Append(')');
			return str.ToString();
		}

		public override bool Equals(object o)
		{
			if (!(o is List))
				return false;
			List that = o as List;
			Expression e1 = child;
			Expression e2 = that.child;
			while (e1 != null && e2 != null)
			{
				if (!e1.Equals(e2))
				{
					return false;
				}
				e1 = e1.Next;
				e2 = e2.Next;
			}
			if (e1 != null || e2 != null)
				return false;
			return true;
		}

		public override int GetHashCode()
		{
			int code = 0;
			for (Expression e = child; e != null; e = e.Next)
				code += e.GetHashCode();
			return code;
		}

		public Expression First  // "car"
		{
			get { return child; }
		}

		public Expression Second // "cadr"
		{
			get
			{
				if (child == null)
					return null;
				return child.next;
			}
		}

		public List Rest  // "cdr"
		{
			get
			{
				if (child == null)
					return new List(null);
				return new List(child.next);
			}
		}
    }
}